package SortAlgorithm;

import com.alibaba.fastjson.JSON;

public class 归并排序 implements ISort {

    /**
     * 分: 分列成一个个子数组后排序  治: 然后再将子数组们融合排序。
     */

    @Override
    public int[] sort(int[] arr) {
        return this.mergeSort(arr);
    }

    public int[] mergeSort(int[] arr) {

        //分配一个辅助数组
        int[] tempApp = new int[arr.length];
        this.mSort(arr, tempApp, 0, arr.length - 1);
        return arr;
    }

    /**
     * 1. 左右一直递归拆分
     * 2. 然后开始合并
     */
    private void mSort(int[] arr, int[] tempArr, int left, int right) {

        //只有一个元素就无需划分,因为一个元素就是有序的
        if (left >= right) {
            return;
        }
        //中间点
        int mid = (right - left) / 2 + left;
        //递归划分左右区域 (分:拆分的过程)
        this.mSort(arr, tempArr, left, mid);
        this.mSort(arr, tempArr, mid + 1, right);
        //划分完之后就进行合并 (治:合并的过程)
        this.merge(arr, tempArr, left, right);
    }

    /**
     * [left, right]
     * 每一半是排好序的,现在让他们形成一整个有序的
     */
    private void merge(int[] arr, int[] tempArr, int left, int right) {

        int mid = (right - left) / 2 + left;

        //标记左半区第一个未排序的元素
        int lPos = left;
        //标记右半区第一个未排序的元素
        int rPos = mid + 1;

        //优化点,前端尾比后端头小,那么这两段就可以不用进行排序
        if (arr[mid] <= arr[mid + 1]) {
            return;
        }

        //临时数组的下标
        int pos = left;

        //合并 条件:左半区有元素&&右半区也有元素
        while (lPos <= mid && rPos <= right) {
            // 如果左半区没有排序的第一个元素小于右半区没有排序的第一个元素,那就将左半区放入临时数组里
            if (arr[lPos] <= arr[rPos]) {
                tempArr[pos++] = arr[lPos++];
            } else {
                // 否则就放入右半区的元素
                tempArr[pos++] = arr[rPos++];
            }
        }

        //上方while是&&的,跳出后可能还有剩余的元素未划分
        //合并左半区剩余的元素
        while (lPos <= mid) {
            tempArr[pos++] = arr[lPos++];
        }

        //合并右半区剩余的元素
        while (rPos <= right) {
            tempArr[pos++] = arr[rPos++];
        }

        //把临时数组中合并后的元素复制回原来的数组
        while (left <= right) {
            arr[left] = tempArr[left++];
        }

    }

    public static void main(String[] args) {
        归并排序 n = new 归并排序();
        int[] arr = {5, 2, 3, 4, 5, 1, 2, 5, 6, 7, 8, 2, 3, 5, 7, 0};
        int[] result = n.mergeSort(arr);
        System.out.println(JSON.toJSONString(result));
    }

}
